#!/usr/bin/env python

# Copyright (c) 2014 Wesley Wiedenmeier <wesley.wiedenmeier@gmail.com>
#
# Permission is hereby granted, free of charge, to any person obtaining a copy of
# this software and associated documentation files (the "Software"), to deal in
# the Software without restriction, including without limitation the rights to
# use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
# of the Software, and to permit persons to whom the Software is furnished to do
# so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.

from math import floor
from random import choice

class Cell():

    def __init__(self, value, row, column, dimension, puzzle):
        self.row = row
        self.column = column
        self.dimension = dimension
        self.puzzle = puzzle
        self.peers = []

        if value != "?":
            self.value = value
        else:
            self.value = None

        if self.value == None:
            self.set_possible()
            self.puzzle.unknown_cells.append(self)

    def set_possible(self):
        self.possible = [x for x in range(1,self.dimension + 1)]

    def remove_possibility(self, possibility):
        if int(possibility) in self.possible:
            self.possible.remove(int(possibility))
        if len(self.possible) == 1:
            self.set_value(self.possible[0])

    def set_value(self, value):
        if value != "?":
            self.value = value
            self.puzzle.unknown_cells.remove(self)
            self.remove_from_peers()
        else:
            self.value = None

    def get_peers(self):
        del self.peers[:]
        self.peers.extend(list(filter(lambda cell: cell.column == self.column and
            cell != self, self.puzzle.get_all_cells())))
        self.peers.extend(list(filter(lambda cell: cell != self, self.puzzle.rows[self.row])))
        root_dimension = int(self.dimension ** (1/2))
        big_grid_row = floor(self.row / root_dimension)
        big_grid_column = floor(self.column / root_dimension)
        for row in range(big_grid_row * root_dimension, (big_grid_row + 1) * root_dimension):
            desired = self.puzzle.rows[row][big_grid_column * root_dimension :
                    (big_grid_column + 1) * root_dimension]
            filtered = list(filter(lambda cell: cell not in self.peers and
                cell is not self, desired))
            self.peers.extend(filtered)

    def remove_from_peers(self):
        for peer in self.peers:
            if peer in self.puzzle.unknown_cells:
                peer.remove_possibility(self.value)

    def __str__(self):
        return "?" if self.value == None else str(self.value)

class Sodoku:
    unknown_cells = []
    rows = []

    def __init__(self, base=3, values=None):
        if hasattr(self, "rows"):
            del self.rows[:]
            del self.unknown_cells[:]

        self.dimension = base ** 2

        if values != None:
            self.input_values(str(values))
        else:
            for row in range(self.dimension):
                self.rows.append([Cell(None, row, column - 1, self.dimension, self)
                        for column in range(self.dimension)])

        for row in self.rows:
            for cell in row:
                cell.get_peers()

    def attempt_solve(self):
        # Can somebody please explain wtf python has no real do-while
        while True:
            while True:
                prev_unknown_len = len(self.unknown_cells)
                self.prune_possibilities()
                if prev_unknown_len == len(self.unknown_cells):
                    break
            if len(self.unknown_cells) == 0:
                break
            self.unknown_cells[0].set_value(choice(self.unknown_cells[0].possible))

    def input_values(self, values):
        del self.rows[:]
        for row in range(self.dimension):
            new_row = []
            line_vals = values[row * self.dimension:row * self.dimension + self.dimension]
            column = 0
            for val in line_vals:
                column += 1
                new_row.append(Cell(val, row, column - 1, self.dimension, self))
            self.rows.append(new_row)

    def output_values(self):
        result = ""
        for row in self.rows:
            for cell in row:
                result += str(Cell)
        return result

    def get_all_cells(self):
        all_cells = []
        for row in self.rows:
            all_cells.extend(row)
        return(all_cells)
    
    def prune_possibilities(self):
        for cell in self.get_all_cells():
            if cell not in self.unknown_cells:
                cell.remove_from_peers()

    def __str__(self):
        result = ""
        for row in self.rows:
            for cell in row:
                result += " " * (len(str(self.dimension)) - len(str(cell)) + 1) + str(cell)
            result += "\n"
        return result
